#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_INPUT 100

typedef struct flight_{
	int number;
	char* date;
	char* origin;
	char* destination;
	struct passengerslist* passengers;
}flight;

typedef struct passenger_{
	int id;
	char* name;
	struct flightslist* flights;
}passenger;

typedef struct flightslist{
	flight* info;
	struct flightslist* next;
}flights_list;

typedef struct passengerslist {
	passenger* info;
	struct passengerslist* next;
} passengers_list;

flights_list* add_flight(flights_list* flights, int number,char* date, char* origin, char* destination);
passengers_list* add_passenger(passengers_list* passengers, int id, char* name);
void buy_ticket(flights_list* flights, passengers_list* passengers, int number, int id);
void cancel_ticket(flights_list* flights, int number, int id);
void print_flight_list(flights_list* flights);
void print_passengers_list(passengers_list* passengers);
void free_all_allocated_memory(flights_list* flights, passengers_list* passengers);
passengers_list* get_sorted_passengers_list(passengers_list* passengers);
void free_passengers_list(passengers_list* passengers);
int flights_number(passenger* pass);

int main()
{

	int input,flight_number,id;
	passengers_list* all_passengers=NULL,*temp;
	flights_list* all_flights=NULL;
	char origin[MAX_INPUT],destination[MAX_INPUT],passenger_name[MAX_INPUT],date[MAX_INPUT];

	do{
		printf("*************Choose From Menu***************\n1.Add Flight\n2.Add Passenger\n3.Buy Ticket\n4.Cancel Ticket\n5.Sort Passengers List By Number of Flights\n6.Print All Flights\n7.Print All Passengers\n8.Exit\nEnter your choice:\n");
		scanf("%d",&input);
		if(input==1){
			printf("Enter flight number:\n");
			scanf("%d",&flight_number);
			printf("Enter date of departure:\n");
			scanf("%s%*c",date);
			printf("Enter place of origin:\n");
			gets(origin);
			printf("Enter place of destination:\n");
			gets(destination);
			all_flights=add_flight(all_flights,flight_number,date,origin,destination);	
		}
		if(input==2){
			printf("Enter passenger ID:\n");
			scanf("%d%*c",&id);
			printf("Enter passenger name:\n");
			gets(passenger_name);
			all_passengers=add_passenger(all_passengers,id,passenger_name);
		}

		if(input==3){
			printf("Enter flight number:\n");
			scanf("%d",&flight_number);
			printf("Enter passenger ID:\n");
			scanf("%d",&id);
			buy_ticket(all_flights,all_passengers,flight_number,id);
		}
		if(input==4){
			printf("Enter flight number:\n");
			scanf("%d",&flight_number);
			printf("Enter passenger ID:\n");
			scanf("%d",&id);
			cancel_ticket(all_flights,flight_number,id);
		}
		if(input==5){
			temp=get_sorted_passengers_list(all_passengers);
			print_passengers_list(temp);
			free_passengers_list(temp);

		}


		if(input==6)
			print_flight_list(all_flights);

		if(input==7)
			print_passengers_list(all_passengers);
	}
	while(input!=8);

	free_all_allocated_memory(all_flights,all_passengers);

	return 0;
}




flights_list* add_flight(flights_list* flights, int number,char* date, char* origin, char* destination)
{
	struct flightslist *third_flight,*first_flight,*second_flight;

	first_flight = (flights_list*) malloc(sizeof(flights_list));
	second_flight = (flights_list*) malloc(sizeof(flights_list));
	third_flight = (flights_list*) malloc(sizeof(flights_list));
	first_flight->info = (flight*) malloc (sizeof(flight));
	second_flight->info = (flight*) malloc (sizeof(flight));
	third_flight->info = (flight*) malloc (sizeof(flight));
	first_flight->info->date=(char*) malloc (sizeof(char)*(strlen(date)+1));
	second_flight->info->date=(char*) malloc (sizeof(char)*(strlen(date)+1));
	third_flight->info->date=(char*) malloc (sizeof(char)*(strlen(date)+1));
	first_flight->info->origin=(char*) malloc (sizeof(char)*(strlen(origin)+1));
	second_flight->info->origin=(char*) malloc (sizeof(char)*(strlen(origin)+1));
	third_flight->info->origin=(char*) malloc (sizeof(char)*(strlen(origin)+1));
	first_flight->info->destination=(char*) malloc (sizeof(char)*(strlen(destination)+1));
	second_flight->info->destination=(char*) malloc (sizeof(char)*(strlen(destination)+1));
	third_flight->info->destination=(char*) malloc (sizeof(char)*(strlen(destination)+1));
	third_flight->info->number = number;
	strcpy(third_flight->info->date,date);
	strcpy(third_flight->info->origin,origin);
	strcpy(third_flight->info->destination,destination);
	third_flight->next=NULL;
	
	if(flights==NULL)
	{
		flights=third_flight;
		return flights;
	}
	if((flights->info->number)<(third_flight->info->number))
	{
		third_flight->next=flights;
		flights->info=third_flight->info;
	}
	second_flight->info=flights->info;
	for(first_flight->info=second_flight->info;third_flight->info->number<second_flight->info->number;second_flight=second_flight->next)
		first_flight->info=second_flight->info;
	(first_flight->next)=third_flight;
	(third_flight->next)=second_flight;

	

	free(first_flight->info);
	free(second_flight->info);
	free(first_flight->info->date);
	free(second_flight->info->date);
	free(first_flight->info->origin);
	free(second_flight->info->origin);
	free(first_flight->info->destination);
	free(second_flight->info->destination);
	free(first_flight);
	free(second_flight);
	return flights;
}

passengers_list* add_passenger(passengers_list* passengers, int id, char* name)
{
	passengers_list *p1,*p2,*p3;
	p1=(passengers_list*)malloc(sizeof(passengers_list));
	p2=(passengers_list*)malloc(sizeof(passengers_list));
	p3=(passengers_list*)malloc(sizeof(passengers_list));
	p1->info = (passenger*) malloc (sizeof(passenger));
	p1->info->name=(char*)malloc(sizeof(char)*(strlen(name)+1));
	p3->info = (passenger*) malloc (sizeof(passenger));
	p2->info = (passenger*) malloc (sizeof(passenger));
	p2->info->name=(char*)malloc(sizeof(char)*(strlen(name)+1));
	p3->info->name=(char*)malloc(sizeof(char)*(strlen(name)+1));
	p2->info->id=id;
	p2->info->name=(char*)malloc(sizeof(char)*(strlen(name)+1));//malloc name
	strcpy(p2->info->name,name);
	if(!passengers)
	{
		passengers->info=p2->info;
		passengers->next=NULL;
		return passengers;
	}
	if((p2->info->id)<(passengers->info->id))
	{
		p2->next=passengers;
		passengers->info=p2->info;
	}
	for(((p1->info)=(passengers->info))&&((p3->info)=(p1->info));(p2->info->id)<(p3->info->id);(p1=p3)&&(p3=p3->next));
	p2->next=p3;
	p1->next=p2;
	return passengers;
}

void buy_ticket(flights_list* flights, passengers_list* passengers, int number, int id)
{
	flights_list *forflight,*flight1,*lastflight;
	passengers_list *passenger,*lastpass,*forpass;
	
	forflight = (flights_list*) malloc(sizeof(flights_list));
	flight1 = (flights_list*) malloc(sizeof(flights_list));
	lastflight = (flights_list*) malloc(sizeof(flights_list));
	forflight->info = (flight*) malloc (sizeof(flight));
	flight1->info = (flight*) malloc (sizeof(flight));
	lastflight->info = (flight*) malloc (sizeof(flight));
	forflight->info->date=(char*) malloc (sizeof(char)*6);
	flight1->info->date=(char*) malloc (sizeof(char)*6);
	lastflight->info->date=(char*) malloc (sizeof(char)*6);
	forflight->info->origin=(char*) malloc (sizeof(char)*(strlen(flights->info->origin)+1));
	flight1->info->origin=(char*) malloc (sizeof(char)*(strlen(flights->info->origin)+1));
	lastflight->info->origin=(char*) malloc (sizeof(char)*(strlen(flights->info->origin)+1));
	forflight->info->destination=(char*) malloc (sizeof(char)*(strlen(flights->info->destination)+1));
	flight1->info->destination=(char*) malloc (sizeof(char)*(strlen(flights->info->destination)+1));
	lastflight->info->destination=(char*) malloc (sizeof(char)*(strlen(flights->info->destination)+1));



	for(flight1->info=flights->info;flight1->info->number<number;flights=flights->next);//getting to the right flight
	for(passenger->info=passengers->info;passenger->info->id<id;passenger=passenger->next);//getting to the right passenger

	if(!(flight1->info->passengers))//if first passenger
	{
		flight1->info->passengers=passenger;
		passenger->next=NULL;
	}
	else//if not first passenger
	{
		for(lastflight->info->passengers->info=(flight1->info->passengers->info);lastflight->info->passengers->info->id>(passenger->info->id);lastflight->info->passengers=flight1->info->passengers->next)
			forflight->info->passengers->info=lastflight->info->passengers->info;
		passenger->next=lastflight->info->passengers;
		forflight->info->passengers->next=passenger;
	}
	if(!(passenger->info->flights))
	{
		passenger->info->flights=flight1;
		passenger->next=NULL;
	}
	else
	{
		for(lastpass->info->flights=passenger->info->flights;passenger->info->flights<lastpass->info->flights;lastpass->info->flights=lastpass->info->flights->next)
			forpass->info->flights=lastpass->info->flights;
		forpass->info->flights->next=passenger->info->flights;
		passenger->info->flights->next=lastpass->info->flights;
	}
}

void cancel_ticket(flights_list* flights, int number, int id)
{
	flights_list *fl1,*fl2,*flp;
	
	fl1 = (flights_list*) malloc(sizeof(flights_list));
	fl2 = (flights_list*) malloc(sizeof(flights_list));
	flp = (flights_list*) malloc(sizeof(flights_list));
	fl1->info = (flight*) malloc (sizeof(flight));
	fl2->info = (flight*) malloc (sizeof(flight));
	flp->info = (flight*) malloc (sizeof(flight));
	fl1->info->date=(char*) malloc (sizeof(char)*6);
	fl2->info->date=(char*) malloc (sizeof(char)*6);
	flp->info->date=(char*) malloc (sizeof(char)*6);
	fl1->info->origin=(char*) malloc (sizeof(char)*(strlen(flights->info->origin)+1));
	fl2->info->origin=(char*) malloc (sizeof(char)*(strlen(flights->info->origin)+1));
	flp->info->origin=(char*) malloc (sizeof(char)*(strlen(flights->info->origin)+1));
	fl1->info->destination=(char*) malloc (sizeof(char)*(strlen(flights->info->destination)+1));
	fl2->info->destination=(char*) malloc (sizeof(char)*(strlen(flights->info->destination)+1));
	flp->info->destination=(char*) malloc (sizeof(char)*(strlen(flights->info->destination)+1));

	fl1=flights;
	while(fl1->info->number!=number)
	{
		if(fl1->info->number==number)
		{
			while(fl1->info->passengers->info->id!=id)
			{
				fl1->info->passengers=fl1->info->passengers->next;
			}
			flp->info->passengers->info=fl1->info->passengers->info;
			break;
		}
		fl1=fl1->next;
	}
	fl2->info->passengers=flp->info->passengers;
	fl1->info->passengers=fl2->info->passengers->next;
	fl1->info->passengers->next=fl2->info->passengers->next->next;
	while(flp->info->passengers->info->flights->info->number!=number)
	{
		flp->info->passengers->info->flights=flp->info->passengers->info->flights->next;
	}
	fl2->info->passengers->info->flights=flp->info->passengers->info->flights;
	flp->info->passengers->info->flights=fl2->info->passengers->info->flights->next;
}

int nameCompare(passengers_list* Name1, passengers_list* Name2)
{
	char *name1=Name1->info->name, *name2=Name2 ->info->name, ch1, ch2;
	while (*name1!='\0' && *name2!='\0')
	{
		ch1=*name1;
		ch2=*name2;
		if (ch1<ch2)
			return 1;
		else
			if (ch1>ch2)
				return 0;
	name1=name1+1;
	ch1=*name1;
	name2=name2+1;
	ch2=*name2;
	}
	if (ch1)
		return 1;
	return 0;
}


int count_flights (passengers_list *flight)
{
	int mone=0;
	flights_list *temp;
	temp=flight->info->flights;
	while (temp->next)
	{
		mone++;
		temp=temp->next;
	}
	return mone;
}



passengers_list* get_sorted_passengers_list(passengers_list* passengers)
{
	passengers_list *newList, *oldList, *newRun, *temp;

	if (!(newList=((passengers_list*)malloc(sizeof(passengers_list)))))
		exit(1);
	oldList=passengers;
	newList->info=oldList->info;
	newList->next=NULL;
	while (oldList->next)
	{
		oldList=oldList->next;
		if (!(temp=((passengers_list*)malloc(sizeof(passengers_list)))))
			exit(1);
		temp->info=oldList->info;
		temp->next=NULL;
		newRun=newList;
		while ((newRun->next) && (count_flights(newRun->next)>count_flights(temp)))
			newRun=newRun->next;
		if (count_flights(newRun)<count_flights(temp))
		{
			temp->next=newList;
			newList=temp;
		}
		else
		{
			if (newRun->next)
			{
				if (count_flights(newRun->next)==count_flights(temp))
				{
					if (nameCompare(newRun->next,temp)) //checks if the first name comes before the second
					{
						temp->next=newRun->next->next;
						newRun->next->next=temp;
					}
					else
					{
						temp->next=newRun->next;
						newRun->next=temp;
					}
				}
				else
				{
					temp->next=newRun->next;
					newRun->next=temp;
				}
			}
			else
			{
				if (count_flights(newRun)==count_flights(temp))
				{
					if (nameCompare(newRun,temp)) //checks if the first name comes before the second
					{
						temp->next=newRun->next;
						newRun->next=temp;
					}
					else
					{
						temp->next=newRun;
						newRun=temp;
					}
				}
				else
					newRun->next=temp;
			}

		}
	}
	return newList;
}
void free_passengers_list(passengers_list* passengers)
{
	{
	passengers_list *temp3,*temp1,*temp2;
	

	temp1=passengers;
	temp2=passengers->next;
	

	while(temp2!=NULL)
	{
		free(temp1->info->name);

		while(temp1->info->flights)
			{
				temp3->info->flights=temp1->info->flights;
				temp1->info->flights=temp1->info->flights->next;
				free(temp3->info->flights);
			}
		free(temp1->info);

		free(temp1);
	

		temp1=temp2;
		temp2=temp2->next;
	}
	free(temp1->info->name);

		while(temp1->info->flights)
			{
				temp3->info->flights=temp1->info->flights;
				temp1->info->flights=temp1->info->flights->next;
				free(temp3->info->flights);
			}
		free(temp1->info);

		free(temp1);
}

}

void free_all_allocated_memory(flights_list* flights, passengers_list* passengers)
{
	flights_list* pof,*pof2,*pof3;
	passengers_list* pop,*pop2;
	pof=flights;
	pop=passengers;
	

	while(pof)
	{
		pof2=pof->next;
		free(pof->info->origin);
		free(pof->info->date);
		free(pof->info->destination);
		free(pof->info->passengers);
		pof=pof2;
	}
	while(pop)
	{
		pop2=pop->next;
		free(pop->info->name);
		free(pop->info->flights);
		pop=pop2;
	}
}

void print_flight_list(flights_list* flights)
{
	flights_list* pointer;
	while(pointer->next)
	{		printf("Flight Number: %03d Date: %s Origin: %s Destination: %s\n",pointer->info->number,pointer->info->date,pointer->info->origin,pointer->info->destination);
		while(pointer->info->passengers->next)
		{
			printf("       Passenger ID Number: %d Passenger Name: %s/n",pointer->info->passengers->info->id,pointer->info->passengers->info->name);
			pointer->info->passengers=pointer->info->passengers->next;
		}
		pointer=pointer->next;
	}
}

void print_passengers_list(passengers_list* passengers)
{
	passengers_list* pointer=passengers;
	while(pointer->next)
	{
		printf("Passenger ID Number: %d Passenger Name: %s/n",pointer->info->id,pointer->info->name);
		while(pointer->info->flights->next)
		{
			printf("      Flight Number: %03d Date: %s Origin: %s Destination: %s\n",pointer->info->flights->info->number,pointer->info->flights->info->date,pointer->info->flights->info->origin,pointer->info->flights->info->destination);
			pointer->info->flights=pointer->info->flights->next;
		}
		pointer=pointer->next;
		printf("\n");
	}
}
int flights_number(passenger* pass)
{
	int num=0;
	passenger* point;
	point=pass;
	if(point->flights->info)
	{
		num=1;
		while(point->flights->next)
		{
			num=num+1;
			point->flights=point->flights->next;
		}
	}
	return num;
}
